Min Stack

Posted on |

问题描述（难度简单-155）

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.

Example:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

方法一：双数组实现

一个数组作为输入的数值栈（stackArray），另一个数组作为最小值栈（minArray）。minArray[i]表示前i个stackArray中的最小值。每次pop出栈的时候同时pop一下minArray。空间复杂度为O(N)，时间复杂度O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
package P155;

import java.util.ArrayList;
import java.util.List;

class MinStack {
    //通过数组实现栈
    private List<Integer> stackArray;
    //记录最小值，在push和pop的过程中都要更新下当前的最小值
    private List<Integer> minArray;

    /** initialize your data structure here. */
    public MinStack() {
        stackArray=new ArrayList<>();
        minArray=new ArrayList<>();
    }
    
    public void push(int x){
        stackArray.add(x);
        int topIndex=minArray.size()-1;
        //最小栈无元素 直接插入
        if(minArray.size()==0){
            minArray.add(x);
        }
        //最小栈有元素但是栈顶元素比插入元素小 插入栈顶元素
        else if(x>minArray.get(topIndex)){
            minArray.add(minArray.get(topIndex));
        }
        //最小栈有元素但是栈顶元素比插入元素大 插入插入元素
        else {
            minArray.add(x);
        }
    }
    
    public void pop() throws Exception {
        if(stackArray.size()==0) {
            throw new Exception("元素为空");
        }
        stackArray.remove(stackArray.size() - 1);
        minArray.remove(minArray.size() - 1);
    }
    
    public int top() throws Exception {
        if(stackArray.size()==0) {
            throw new Exception("元素为空");
        }
        return stackArray.get(stackArray.size() - 1);
    }
    
    public int getMin() throws Exception {
        if(minArray.size()==0) {
            throw new Exception("元素为空");
        }
        return minArray.get(minArray.size()-1);
    }

    public static void main(String[] args) throws Exception {
        MinStack minStack = new MinStack();
        minStack.push(2);
        minStack.push(0);
        minStack.push(3);
        minStack.push(0);
        minStack.pop();
        System.out.println(minStack.getMin());
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

方法二：双数组实现（缩减空间）

在方法一的基础上，实际上minArray没有必要存储N个最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package P155;

import java.util.ArrayList;
import java.util.List;

/**
 * 改善第一种方式
 * 最小值的数组不需要存全部的结果结
 * @autor yeqiaozhu.
 * @date 2019-10-09
 */
public class MInStackUsingTwoArrayBetter {
    //通过数组实现栈
    private List<Integer> stackArray;
    //记录最小值，在push和pop的过程中都要更新下当前的最小值
    private List<Integer> minArray;

    /** initialize your data structure here. */
    public MInStackUsingTwoArrayBetter() {
        stackArray=new ArrayList<>();
        minArray=new ArrayList<>();
    }

    public void push(int x){
        stackArray.add(x);
        int topIndex=minArray.size()-1;
        //最小栈无元素 直接插入
        if(minArray.size()==0){
            minArray.add(x);
        }
        //最小栈有元素但是栈顶元素比插入元素大 插入插入元素
        else if(x<=minArray.get(topIndex)){
            minArray.add(x);
        }
    }

    public void pop() throws Exception {
        if(stackArray.size()==0) {
            throw new Exception("元素为空");
        }
        int value=stackArray.remove(stackArray.size() - 1);
        if(value==minArray.get(minArray.size()-1)) {
            minArray.remove(minArray.size() - 1);
        }
    }

    public int top() throws Exception {
        if(stackArray.size()==0) {
            throw new Exception("元素为空");
        }
        return stackArray.get(stackArray.size() - 1);
    }

    public int getMin() throws Exception {
        if(minArray.size()==0) {
            throw new Exception("元素为空");
        }
        return minArray.get(minArray.size()-1);
    }

    public static void main(String[] args) throws Exception {
        MInStackUsingTwoArrayBetter minStack = new MInStackUsingTwoArrayBetter();
        minStack.push(2);
        minStack.push(3);
        minStack.push(0);
        minStack.push(0);
        System.out.println(minStack.getMin());
        minStack.pop();
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
        System.out.println(minStack.top());
        minStack.pop();
        System.out.println(minStack.getMin());
    }
}